"""
https://leetcode.cn/problems/path-sum/description/

112. 路径总和
已解答
简单
相关标签
premium lock icon
相关企业
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

 

示例 1：


输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：


输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
 

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    题目中未提及，二叉树节点的顺序性，因此无法利用
    同时也提及节点值允许为负数，因此如果找不到匹配路径，几乎需要一直遍历。

    仍是按照二叉树的遍历方法基础上改造。
    
    同时需要注意：题目要求从叶子节点到根节点，因此还必须遍历完。
    """

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        def itr(node,target):
            if not node.left and not node.right:
                return target==node.val
            new_target=target-node.val
            # print(f'{node.val}->{new_target}')
            if node.left and itr(node.left,new_target):
                return True
            if node.right and itr(node.right,new_target):
                return True
            return False
        
        return itr(root,targetSum)

if __name__=='__main__':
    arr=[1,2]
    root=build_tree_node(arr)
    target_sum=0

    s=Solution()
    res=s.hasPathSum(root,target_sum)
    print(res)